# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next


class Solution:
    def connect(self, root: 'Node') -> 'Node':
        def findfirstright(node):
            if node.left is not None:
                return node.left
            if node.right is not None:
                return node.right
            if node.next is not None:
                return findfirstright(node.next)
            return None
        def connectnode(parent,node,flag):
            if flag:
                if parent.right is None and parent.next is not None:
                    node.next=findfirstright(parent.next)
                else:
                    node.next=parent.right
            elif parent is not None and parent.next is not None:
                node.next=findfirstright(parent.next)
            if node.right is not None:
                connectnode(node,node.right,False)
            if node.left is not None:
                connectnode(node,node.left,True)
        if root is None:
            return root
        connectnode(None,root,False)
        return root
            